package com.leetcode.string;

/*
验证回文串
给定一个字符串，
验证它是否是回文串，
只考虑字母和数字字符，可
以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
示例 2:
输入: "race a car"
输出: false
解释："raceacar" 不是回文串

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xne8id/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class IsPalindromeTest {
    public static void main(String[] args) {
        String s = "race a car";
        //String s = "A man, a plan, a canal: Panama";
        boolean palindrome = isPalindrome3(s);
        System.out.println(palindrome);
    }

    /**
     * 1 将字符串首先筛选出来,去掉除字母和数字以外的字符
     * 使用StirngBuffer与character完成以上步骤
     * 2使用reverse将字符串反转
     * 3使用String类的equals方法判断是否一致
     * @param s
     * @return
     */
    public static boolean isPalindrome(String s) {
        //筛选字符串
        //创建StringBuffer对象
        StringBuffer str = new StringBuffer();
        //遍历字符串
        for (int i = 0; i < s.length(); i++) {
            //判断是否为字母或者数字
            if(Character.isLetterOrDigit(s.charAt(i))){
                //判断成立,添加到str中,本体忽略大小写,将字符转为小写
                str.append(Character.toLowerCase(s.charAt(i)));
            }
        }
        //创建新的Stringbuffer对象保存反转字符串
        StringBuffer reverse = new StringBuffer(str).reverse();
        //调用String的equals方法判断是否一致
        return str.toString().equals(reverse.toString());
    }

    /**
     * 使用双指针的方法
     * 1 筛选字符串,保留其中的字母或者字符
     * 2 创建两个指针,一个在头,一个在尾开始
     * 3 判断当前两个指正位置的字符是否相等
     * 4 若相等,则头指正++,尾指针--
     * 若不同 返回 false
     * 5 两指正相遇,返回TRUE,跳出循环
     * @param s
     * @return boolean
     */
    public static boolean isPalindrome2(String s) {
        //筛选字符串
        //创建StringBuffer对象
        StringBuffer str = new StringBuffer();
        //遍历字符串
        for (int i = 0; i < s.length(); i++) {
            //判断是否为字母或者数字
            if(Character.isLetterOrDigit(s.charAt(i))){
                //判断成立,添加到str中,本体忽略大小写,将字符转为小写
                str.append(Character.toLowerCase(s.charAt(i)));
            }
        }
        //循环判断两指针位置的字符
        for (int first = 0,end= str.length()-1; first < end; first++,end--){
            //忽略大小写的判断,一旦不相等,返回false
            if (Character.isLowerCase(str.charAt(first)) !=
            Character.isLowerCase(str.charAt(end))){
                return false;
            }
        }
        //循环结束返回true
        return true;
    }

    /**
     * 1 使用双指针的方法,一个在字符串的头部,一个在字符串尾部
     * 2 循环过程首先判断两个指针指向的字符是否是数字或者字符
     * 不是的话,头指正++,尾指针--
     * 3 判断两指针处的字符是否忽略大小写不相等,返回false
     * 4 循环完成,返回true
     * @param s
     * @return
     */
    public static boolean isPalindrome3(String s) {
        //创建两个指针,完成循环
        for (int first = 0,end= s.length()-1; first < end; first++,end--){
            //将两个指针指向数字或者字符,可能会有多次无法指向,需要变动,使用循环
            //在循环过程中,会使指针的位置发生变动,可能在变动的过程中,使外循环的判断出现false
            //故在内循环和判断指针位置时,判断外循环的条件是否成立
            while (first < end && !Character.isLetterOrDigit(s.charAt(first))){
                first++;
            }
            while (first < end && !Character.isLetterOrDigit(s.charAt(end))){
                end--;
            }
            //判断两指针指向字符是否一致
            if (first < end){
                if (Character.toLowerCase(s.charAt(first)) !=
                        Character.toLowerCase(s.charAt(end))){
                    return false;
                }
            }
        }
        //循环结束返回true
        return true;
    }
}
